1. Field of Invention
This invention relates to a method and system for allocating bandwidth in a communication network.
2. Description of Related Art
Communication networks use a variety of network elements to route signals from an originating point to a terminating point. One common network element is a switch, such as a COREDIRECTOR™ switch available from CIENA Corporation, that directs signals from one link (e.g., an optical fiber) to another. FIG. 1 depicts a portion of an exemplary optical communication network including terminals 10 and 12 optically communicating through switches A–D. Typically, switches have a plurality of inputs and a corresponding plurality of outputs. When a connection is requested from terminal 10 to terminal 12, switches A–D establish the connection.
Each switch A–D includes ingress ports and egress ports. The signal transmitted on the optical communication network is often time-division mutliplexed (TDM). Thus, there must be coordination between switches so that the signal is allocated to defined time slots. For example, for a signal to be transmitted from an egress port on switch A to an ingress port on switch B, switches A and B need to have the same time slot(s) available for this signal. Existing switches have the ability to change time slots within the switch, but between switches, the egress time slot and ingress time slot must match.
The process of establishing a connection from terminal 10 to terminal 12 is conventionally performed in two phases, namely a set-up phase and a connect phase. During set-up phase, the switches A–D make a rough determination of bandwidth availability based on congestion on the network. During the connect phase, the switches allocate time slots, create cross connects, and program the logical switch.
For example, assume a request for a connection is generated at terminal 10. During the set-up phase, switch A generates a set-up message flows from switch A to switch D. Each switch A–D checks for available bandwidth and issues a release message if the bandwidth is not available. No actual bandwidth allocation is performed during the set-up phase nor is there a determination of whether a pair of ports connected by a link has the same set of available time slots. The purpose of the set-up message is to make a rough determination of whether or not this connection can be admitted under the current network conditions.
If the set-up message is processed by all switches without a release message being generated, the connect phase is initiated and a connect message is sent from switch D to switch A. In the connect phase, each switch checks for the availability of matching time slots on a pair of ports connected by a link. As an example, switch D computes a set of available time slots at an ingress port and forwards these time slots to an egress port on switch C. Switch C, upon receiving these time slots, checks if these are available on the egress port. If this check succeeds, then the connect message is forwarded to an ingress port of switch C. If the ingress port of switch C has a set of available time slots (not necessarily the same time slots reserved at the egress port), switch C forwards these time slots to an egress port on switch B. Switch C also creates a cross connection (e.g., from egress port to ingress port), programs the logical switch, and saves this information. The connect phase continues until either a switch lacks available time slots, at which time the connection is not established, or the connection is established at all switches.
The existing process of establishing a connection suffers some drawbacks. One drawback is the possibility of creating a livelock situation if two switches are each trying to create connections on the same link. Consider, for example, the case when switch A and switch D are both trying to set up connections, one from switch A to switch D and another from switch D to switch A. Assume a first connect message from switch A reaches switch B at the same time as the second connect message from switch D reaches switch C. Switches B and C will attempt to reserve overlapping sets of time slots at which point both switches B and C receive release messages from one another. At this point, switch A and switch D are notified that the connection was not established and both switch A and switch D may again request a connection. This situation may repeat a number of times, resulting in a livelock situation. The livelock situation prevents establishment of connections and results in network signals being dropped.
Another drawback to the existing set-up and connect process is the creation of one-sided or orphan connections. A one-sided connection refers to a connection having only one endpoint. Referring to a connect message from switch D to switch A, if switch C proposes a set of time slots to switch B and some of these time slots are being occupied by a one-sided connection on switch B, then a livelock situation may arise where the connection request is repeatedly denied.
Another drawback to the existing set-up and connect process is the length of delay in releasing a connection request. Consider a situation where switch A has requested several connections involving the same link but the available capacity on the link allows at most one connection. During the set-up phase, all the requested connections will be admitted because there is no confirmation of bandwidth or of available time slots during the set-up phase. In the connect phase, however, all but one of the requested connections will be denied due to the bandwidth limit. It is preferable to deny requested connections promptly to limit delay in establishing the connection. Similarly, it is preferable to establish a connection as early as possible. The existing set-up and connect process does not expedite denying or establishing connections.